package _022_1_29

import "sort"

type canThanListNodeP struct {
	nodes []*ListNode
}

func (this *canThanListNodeP) Less(i, j int) bool {
	if this.nodes[i].Val < this.nodes[j].Val {
		return true
	}
	return false
}

func (this *canThanListNodeP) Swap(i, j int) {
	temp := this.nodes[i]
	this.nodes[i] = this.nodes[j]
	this.nodes[j] = temp
}

func (this *canThanListNodeP) Len() int {
	return len(this.nodes)
}
func mergeKLists2(lists []*ListNode) *ListNode {
	listNode := canThanListNodeP{
		nodes: make([]*ListNode, 0),
	}

	for i := 0; i < len(lists); i++ {
		for lists[i] != nil {
			listNode.nodes = append(listNode.nodes, lists[i])
			lists[i] = lists[i].Next
		}
	}

	sort.Sort(&listNode)
	head := ListNode{
		Next: nil,
	}
	tail := &head
	for i := 0; i < len(listNode.nodes); i++ {
		tail.Next = listNode.nodes[i]
		tail = tail.Next
		tail.Next = nil
	}
	return head.Next
}
